/**
 * @Author Fizz Pu
 * @Date 2020/9/15 下午8:40
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// 此题输入简直了,不做也罢
import java.util.*;

/**
 * 每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/baby-names-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 在结果列表中，选择字典序最小的名字作为真实名字。
 *
 * 示例：
 *
 * 输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
 * 输出：["John(27)","Chris(36)"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/baby-names-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

// 这个有点香啊! 相同关系的关系的归为一组,很明细的并查集合
public class Lee1707 {
    public static void main(String[] args) {
        String[] names = {"John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"},
        synonyms = {"(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"};
        new Lee1707().trulyMostPopular(names, synonyms);
    }
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        // 处理一下names数组
        Map<String, Integer> map = new HashMap<>();
        // 数据处理
        for(String name: names){
            int length = name.length();
            String rate = name.substring(name.indexOf('(') + 1, name.indexOf(')')); //处理字符串,subString和indexOf一起使用
            String realName = name.substring(0, name.indexOf('('));
            map.put(realName,Integer.parseInt(rate));
        }

        // 并查集,合并关系
        DefineUnionSearchSet unionSearchSet = new DefineUnionSearchSet(map.keySet()); // 由hashmap直接得到一个set,oh,这太棒了
        for(String relation: synonyms){
            String name1= relation.substring(1,relation.indexOf(','));
            String name2= relation.substring(relation.indexOf(',')+1,relation.length()-1);
            if(!map.containsKey(name1) || !map.containsKey(name2))continue;
            unionSearchSet.union(name1,name2);
        }

        // 查找分类
        Map<String , String> roots = unionSearchSet.getRoots();
        return null;
    }
}


// 自定义并查集
class DefineUnionSearchSet {

    public HashMap<String, String> getRoots() {
        return roots;
    }

    private HashMap<String,String> roots;

    // 初始化时，用hashmap存储父节点
    public DefineUnionSearchSet(Set<String> hashSet) {
        roots = new HashMap<>(hashSet.size());
        var iterator = hashSet.iterator();
        while (iterator.hasNext()){
            // roots.put(iterator.next(),iterator.next()); watch out! 使用迭代器時，不要調用next()兩次
            String ele = iterator.next();
             roots.put(ele,ele);
        }
    }

    // 合并
    public void union(String ele1, String ele2) {
        String x = find(ele1);
        String y = find(ele2);
        if (!x.equals(y)) { // 不是同一个集合就合并
            // roots.put(x, y); // 相当于x的父亲是y
            // 此处不能乱合并,要遵循一定的规则, 字典序排序小的作为父亲
            if(x.compareTo(y) > 0){
                roots.put(x,y);
            }else {
                roots.put(y,x);
            }
        }
    }

    // 查找
    // 利用路径压缩优化查找算法
    public String find(String element) {
        if (element.equals(roots.get(element))) {
            return element;
        }
        String father = find(roots.get(element));
        roots.put(element,father);
        return father;
    }

    // 判断是否属于同于集合
    public boolean sameSet(String ele1, String ele2){
        return find(ele1).equals(find(ele2));
    }
    //  返回拥有的haspmap
}
